给定一个包含 N 个正整数的集合,请你将它划分为两个集合 A1 和 A2,其中 A1 包含 n1 个元素,A2 包含 n2 个元素。集合中可以包含相同元素。用 S1 表示集合 A1 内所有元素之和,S2 表示集合 A2 内所有元素之和。请你妥善划分,使得∣n1−n2∣ 尽可能小,并在此基础上∣S1−S2∣ 尽可能大。
2≤N≤105, 保证集合中各元素以及所有元素之和小于 231。
输入格式:
第一行包含整数 N。 第二行包含 N 个正整数。
输出格式:
在一行中输出 ∣n1−n2∣ 和 ∣S1−S2∣,两数之间空格隔开。
输入样例1:
1 2
| 10 23 8 10 99 46 2333 46 1 666 555
|
输出样例1:
输入样例2:
1 2
| 13 110 79 218 69 3721 100 29 135 2 6 13 5188 85
|
输出样例2:
思路
将一个集合划分为S1和S2两个集合,首先使两集合元素总数的差尽可能小,在此基础上使两集合元素和的差尽可能小
两集合元素总数的差尽可能小,即尽可能趋于0。
- 原集合的元素总数为偶数,则可S1和S2各分配一半元素;
- 原集合的元素总数为奇数,为满足两集合元素和的差尽可能小,使一个集合元素比另一个集合元素数多1即可满足
利用sort给集合排序,后半边的数存入S2,前半边存入S1,即可满足两集合元素和的差尽可能小
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include <iostream> #include <algorithm>
using namespace std;
int get_sum(int i, int j, int *ve) { int ret = 0; for(int k = i; k <= j; k++) { ret += ve[k]; } return ret; }
int main() { int n; scanf("%d", &n); int ve[n]; for(int i = 0; i < n; i++) { scanf("%d", &ve[i]); } sort(ve, ve+n); if(n % 2 == 0) { printf("0 "); printf("%d\n", get_sum(n / 2, n - 1, ve) - get_sum(0, n / 2 - 1, ve)); } else { printf("1 "); printf("%d\n", get_sum(n / 2, n - 1, ve) - get_sum(0, n / 2 - 1, ve)); } return 0; }
|